ノード構造を定義し、主要なポインタ操作の効率を分析することで、連結リストの基礎を築きます。
- 先ほど観察した構造上の違い——特に動的ポインタの使用——により、頻繁な挿入や削除が必要な用途において、連結リストは非常に強力なツールとなります。複雑なアルゴリズムに進む前に、この構造の定義と基本的な動作原理について確固たる基礎を築く必要があります。
- 今回の講義セクションでは、連結リストの習得に専念します。私たちのロードマップが、その基本概念と古典的なデータ構造問題への実用的応用を導いていきます：
- 目標：サイズ $n$ が変動的または不明な場合に、なぜ連結リストが選ばれるのかを理解し、効率が ポインタの再接続ではなくメモリのシフトに依存するかを理解することです。
- ロードマップ概要：
- 1. 構造と定義： まず正式に ノード構造（データ項目と $next$ ポインタ）を定義し、単方向、双方向、循環型連結リストの違いを検討します。
- 2. コア操作： ポインタの操作をマスターする：
- 走査：リストを順番にアクセスする操作で、$O(n)$ の時間が必要です。
- 挿入：既知の位置 $i$ にノードを追加する操作で、$next$ ポインタを調整することで、効率的な $O(1)$ 時間で行えます。ポインタ再接続色に依存するかを理解することです。
- 削除：ノードを削除し、ポインタを調整する操作も、$O(1)$ で可能です。
- 3. 例題としての応用（多項式）： 連結リストを使って代数的な多項式を格納・操作します。各ノードは 多項式項 ($\langle 系数, 指数 \rangle$) を保持します。これにより、連結リストが動的構造管理において優れている点、特に多項式の加算（通常 $O(n+m)$ 時間で実行される）においての長所が示されます。
連結リストのコア操作の計算量
| 操作 | 説明 | 計算量 |
|---|---|---|
| 走査 | 要素の探索またはリストの終端の検出。 | $O(n)$ |
| 挿入（既知の位置 $i$ にて） | 2つのポインタの調整。 | $O(1)$ |
| 削除（既知の位置 $i$ にて） | 1つのポインタの調整。 | $O(1)$ |